\chapter*{Estratto in lingua italiana}
\markboth{Estratto in lingua italiana}{}
\addcontentsline{toc}{chapter}{Estratto in lingua italiana}

\begin{flushright}
\sl
As many more individuals of each species are born than can possibly survive, and as consequently there is a frequently recurring struggle for existence, it follows that any being, if it vary in any manner profitable to itself, under the complex and sometimes varying conditions of life, will have a better chance of survival and thus be naturally selected. From the strong principle of inheritance, any selected variety will tend to propagate its new and modified form. [Introduction, p. 5]
\end{flushright}

\begin{flushright}
\sl
C. Darwin, \textit{Origin of Species}
\end{flushright}

\par\vfill\par


La \textit{sintesi ad alto livello} si occupa del progetto e dell'implementazione di circuiti digitali a partire da una descrizione comportamentale, soggetta a un insieme di obiettivi e vincoli, a partire da una libreria contenente i diversi tipi di risorse che possono essere utilizzate.

La sintesi ad alto livello \`{e} principalmente composta da tre sottoproblemi:
\begin{enumerate}
 \item Assegnamento \textit{temporale} delle operazioni: fornisce i passi di controllo nei quali ogni operazione inizia la sua esecuzione.
\item Assegnamento \textit{spaziale} delle operazioni: riguarda l'assegnamento delle operazioni e dei valori ai componenti fisici e l'interconnessione degli stessi attraverso specifici componenti di libreria. Risolvere questi problemi in modo efficiente non \`{e} questione di poco conto, dal momento che si \`{e} dimostrato che tutti questi sono NP-completi~\cite{np_complete}.
\item Sintesi del \textit{controllore}: fornisce la logica per abilitare le operazioni nell'unit\`{a} di elaborazione, in relazione al flusso di controllo.
\end{enumerate}

Studi recenti~\cite{interconnection_cong} hanno dimostrato che il costo delle interconnessioni deve necessariamente essere tenuto in considerazione, dal momento che l'area degli elementi di selezione e interconnessione ha oramai superato, e di molto, l'area delle unit\`{a} funzionali e dei registri. Queste considerazioni sono particolarmente fondate nel caso di progetti orientati ai dispositivi logici riprogrammabili, dal momento che deve essere fornito un  un elevato numero di transistori per i canali di comunicazione e le celle logiche, in modo da poter programmare la trasmissione dei segnali. Questo giustifica fortemente il progetto di algoritmi altamente efficienti per la riduzione del numero e della dimensione degli elementi di selezione, generati dalla sintesi ad alto livello: una metodologia che non li tiene in considerazione porta evidentemente ad una stima d'area incompleta. Questo potrebbe condurre quindi a scelte di progetto errate, dove gli elementi di interconnessione potrebbero influenzare in maniera significativa i costi d'area totali, tanto da superare i vincoli imposti. Infatti, talvolta soluzioni architetturali con pi\`{u} unit\`{a} funzionali o registri potrebbero ridurre paradossalmente l'area totale, poich\'e riducono in maniera significativa l'utilizzo degli elementi di interconnessione. Di conseguenza, l'allocazione delle interconnessioni deve necessariamente essere tenuta in conto in ogni metodologia che provi a minimizzare l'occupazione di area di un specifica implementata su dispositivi riprogrammabili.

\ \\
L'obiettivo di questa tesi \`{e} quello di produrre una metodologia per affrontare il problema della sintesi ad alto livello, che sia in grado di tenere in considerazione il contributo di area dato da tutti gli elementi che costituiscono l'architettura. La metodologia deve cos\`{\i} poter esplorare lo spazio di progetto architetturale in modo da poter trovare le soluzioni che riducano l'area totale richiesta dall'implementazione finale della specifica.

Gli algoritmi evolutivi sono buoni candidati per affrontare il problema della sintesi ad alto livello e dell'esplorazione dello spazio di progetto dal momento che tendono a migliorare in modo iterativo un insieme di soluzioni (cio\`{e} le alternative di progetto), non richiedono che la funzione di qualit\`{a} (o di costo, a seconda dei casi) sia lineare ed \`{e} provato che lavorano molto bene su problemi con spazi di ricerca molto estesi e non convessi (es: in situazioni nelle quali sono stati specificati dei vincoli oppure sono disponibili poche informazioni sul problema). Possono anche costruirsi \textit{autonomamente} un modello per poter dare una stima sulla soluzione finale.

La funzione di costo considerata, per il problema della sintesi ad alto livello, \`{e} composta da due obiettivi, che devono essere ottimizzati simultaneamente: l'area e le prestazioni. Per questo motivo, \`{e} stato proposto un modello per fornire delle stime sui valori di questi obiettivi per le soluzioni che risultano dall'applicazione del flusso. Il modello \`{e} stato creato in modo da essere orientato a ottenere buoni risultati per la sintesi su dispositivi riprogrammabili.

Poich\'e la funzione di costo da essere ottimizzata \`{e} una funzione a pi\`{u} obiettivi, la soluzione proposta utilizza si basa sull'algoritmo NSGA-II~\cite{deb00fast}, dal momento che questo \`{e} in grado di mantenere una certa diversit\`{a} all'interno della popolazione e, inoltre, consente di effettuare una migliore esplorazione in uno spazio di progetto a pi\`{u} obiettivi. Questo \`{e} dovuto al fatto che i singoli criteri da ottimizzare sono pesati per ridurre la funzione a un singolo obiettivo, come combinazione lineare degli stessi. In questo algoritmo, tutti gli obiettivi sono considerati allo stesso livello. Per altro, non c'\`{e} una \textit{singola} soluzione a questo genere di problemi, cio\`{e} non ci si pu\`{o} aspettare un \textquotedblleft ottimo\textquotedblright~nel senso tradizionale. Al contrario, c'\`{e} un \textit{insieme} di soluzioni alternative, che rappresentano i diversi bilanciamenti dei vari obiettivi. Quindi, fra queste soluzioni, verr\`{a} scelta quella che meglio si adatta ai vincoli di area imposti dal dispositivo su cui verr\`{a} effettuata la sintesi logica finale.

I maggiori contributi di questo lavoro si possono cos\`{i} riassumere:
\begin{itemize}
 \item un \textbf{flusso di sintesi ad alto livello}, che è in grado di tradurre la specifica comportamentale da linguaggio C ad alto livello direttamente in una specifica strutturale a livello RTL (Register Transfer Level), che pu\`{o} essere descritta con differenti linguaggi per la descrizione architetturale (es: SystemC, VHDL o Verilog);
\item un \textbf{modello}, stato usato per la valutazione dei risultati provenienti dalla sintesi ad alto livello, che presenta un errore limitato rispetto ai valori che derivano dalla sintesi effettiva su dispositivi riprogrammabili;
\item un algoritmo di \textbf{esplorazione architetturale}, basato su un algoritmo genetico che integra le potenzialit\`{a} dell'algoritmo NSGA-II ed \`{e} in grado di trattare problemi di ottimizzazione a pi\`{u} obiettivi. Inoltre, dal momento che integra il flusso di sintesi di alto livello nella valutazione della funzione di costo, \`{e} in grado di considerare il contributo dato da tutte le componenti che costituiranno l'architettura finale. In questo modo, \`{e} stato possibile tenere in considerazione anche gli elementi di interconnessione, che possono essere cos\`{i} ridotti attraverso un particolare assegnamento delle operazioni alle unit\`{a} funzionali.
\end{itemize}

\ \\
Questa tesi \`{e} organizzata nel modo seguente. Nel Capitolo~\ref{preliminaries}, il problema della sintesi ad alto livello \`{e} formulato e formalizzato. Quindi sono presentati gli elementi costituenti un algoritmo genetico. Il Capitolo~\ref{state_art} fornisce una panoramica sull'attuale stato dell'arte per quanto riguarda le tecniche di sintesi ad alto livello e gli algoritmi genetici (es: l'algoritmo NSGA-II). Sono anche presentati alcuni approcci esistenti che integrano gli algoritmi evolutivi in un flusso di sintesi ad alto livello. Nel Capitolo~\ref{mixed}, viene presentato il flusso di sintesi che integra i due componenti: la sintesi ad alto livello e l'esplorazione dello spazio architetturale. Inoltre, sono motivate le scelte implementative adottate. Quindi, nel Capitolo~\ref{details}, il flusso di sintesi e l'esplorazione dello spazio di progetto sono dettagliati. Ogni componente \`{e} analizzato e descritto in modo da poter comprendere come \`{e} stato implementato. I risultati sperimentali ottenuti sono riportati nel Capitolo~\ref{results}. Infine, nel Capitolo~\ref{conclusions}, viene commentata la metodologia proposta e vengono proposti alcuni possibili sviluppi futuri che potrebbero estenderne le potenzialit\`{a}.


\section*{Risultati sperimentali e conclusioni}
\addcontentsline{toc}{section}{Risultati sperimentali e conclusioni}

La metodologia proposta \`{e} stata implementata e integrata in un ambiente di sviluppo esistente, chiamato \textit{PandA}~\cite{panda}, sviluppato per coprire diversi aspetti della co-sintesi di specifiche comportamentali e strutturali. L'intera metodologia \`{e} stata sviluppata in linguaggio C++ e, per quanto riguarda la computazione evolutiva, si \`{e} utilizzata la libreria \textit{OPEN Beagle}~\cite{openbeagle}. Questa libreria offre la possibilit\`{a} di effettuare un ampio insieme di computazioni evolutive, con un supporto per differenti algoritmi genetici (fra i quali l'algoritmo NSGA-II) e la possibilit\`{a} di estendere le codifiche degli individui a seconda delle esigenze.

I risultati del flusso di sintesi sono stati validati sia in modo comportamentale, per verificare che il comportamento implementato sia effettivamente coerente con quello richiesto dalla specifica, sia in modo strutturale, attraverso la sintesi, sfruttando lo strumento ISE ver. 8.1i della Xilinx~\cite{Xilinx}, su un dispositivo riprogrammabile fisico (\`{e} stato scelto, come dispositivo FPGA, il Virtex II-PRO XC2VP30 della Xilinx). I risultati hanno dimostrato che il flusso di sintesi proposto \`{e} stato in grado di generare specifiche strutturali coerenti dal punto di vista comportamentale e correttamente sintetizzabili dal punto di vista strutturale. Il modello d'area proposto \`{e} stato inoltre in grado di effettuare delle stime che, in relazione ai valori realmente derivanti dalla sintesi fisica su scheda, mostrano un errore medio intorno al 4\%, mentre l'errore massimo \`{e} inferiore al 10\%. Questo giustifica la scelta di usare il flusso di sintesi, in unione a questo modello di stima, per la valutazione delle soluzioni esplorate dall'algoritmo genetico. L'applicazione della metodologia proposta ha dimostrato, su alcuni esempi, un risparmio che pu\`{o} arrivare anche a circa il 20\% dell'area inizialmente richiesta, tenendo in considerazione tutti gli elementi fisici che andranno a comporre l'implementazione finale, quindi anche gli elementi di interconnessione.

Inoltre si evidenzia che la metodologia proposta, composta da un flusso di sintesi e un algoritmo genetico per l'esplorazione architetturale, \`{e} effettivamente applicabile, con buoni risultati, anche a problemi reali di interesse, come la sintesi di moduli strutturali per accelerare alcune fasi della compressione JPEG.

In definitiva, la metodologia proposta soddisfa le necessit\`{a} per le quali era stata progettata, anche se presenta delle limitazioni. In primo luogo, i costrutti ciclici non sono al momento supportati, dal momento che richiederebbero agli algoritmi di essere in grado di trattare operazioni che potrebbero essere o non essere eseguite a seconda del flusso di controllo. Questo potrebbe portare, ad esempio, a uno spreco di risorse nel momento in cui queste operazioni non vengano pi\`{u} eseguite. 
Inoltre la specifica, al momento, non \`{e} in grado di supportare l'accesso a memoria, in quanto l'algoritmo di assegnamento temporale non \`{e} in grado di trattare operazioni a latenza indefinita. 
Quindi, il modello proposto della stima dovrebbe essere raffinato, per poter produrre valori con un margine di errore sempre pi\`{u} ridotto rispetto ai valori reali. Inoltre potrebbe essere interessante ottimizzare i parametri del modello in relazione allo strumento di sintesi effettivamente utilizzato e dal dispositivo finale, in quanto tecnologie diverse potrebbero condurre lo strumento di sintesi a soluzioni differenti.
Infine, quando cresce la complessit\`{a} delle specifiche comportamentali da esplorare, il tempo di esecuzione della sintesi ad alto livello cresce notevolmente e, dal momento viene eseguito un flusso di sintesi ad ogni valutazione di un individuo, il tempo di esecuzione dell'esplorazione architetturale tende a valori spesso inaccettabili. Una soluzione potrebbe essere quella di adottare, in certi casi, dei surrogati della funzione di valutazione, sfruttando gli algoritmi di stima delle distribuzioni di probabilit\`{a}~\cite{sastry01evaluationrelaxation,sastry01dont,sastry2006} sviluppati per sostituire funzioni di valutazione costose, con delle stime derivanti dall'analisi delle distribuzioni di probabilit\`{a} delle soluzioni gi\`{a} valutate.




